#ifndef __SKIPLIST_HEAD__
#define __SKIPLIST_HEAD__

#include <cstdlib>
#include <iostream>
using namespace std;

// 跳表节点
template<class SLKT, class SLVT>
struct SkipListNode
{
	struct SkipListNode** m_ptlist;
	const SLKT& m_key;
	SLVT& m_value;
	unsigned int m_level;
	bool m_ishead;
	
	SkipListNode(unsigned int level)
		:m_key(),m_value()
	{
		if(level<1 || level>16)
		{
			this->m_level = 1;
		}

		this->m_ptlist = new SkipListNode*[level];
		for(unsigned int i=0;i<this->m_level;++i)
		{
			this->m_ptlist[i] = NULL;
		}
		m_ishead = true;
	}

	SkipListNode(unsigned int level, const SLKT& thekey, SLVT& thevalue)
		:m_key(thekey),m_value(thevalue)
	{
		if(level<1 || level>16)
		{
			this->m_level = 1;
		}

		this->m_ptlist = new SkipListNode*[level];
		for(unsigned int i=0;i<this->m_level;++i)
		{
			this->m_ptlist[i] = NULL;
		}
		m_ishead = false;
	}

	~SkipListNode()
	{
		delete this->m_ptlist;
	}
};

// 跳表类
template<class SLKT, class SLVT>
class SkipList
{
public:
	SkipList(unsigned int maxlevel);
	~SkipList();
	unsigned int getMaxlevel(){return this.m_maxlevel;}
	SkipListNode<SLKT, SLVT>* doSearch(const SLKT& thekey);
	bool doInsert(const SLKT& thekey, SLKT& thevalue, bool doReplaceValue=true);
	bool doDelete(const SLKT& thekey);
	long length();
	void doPrint();
private:
	unsigned int getRandomLevel();
	unsigned int m_maxlevel;
	struct SkipListNode<SLKT, SLVT>* m_listhead;
};

// 构造函数,确定maxlevel，构造链表头
template<class SLKT, class SLVT>
SkipList<SLKT, SLVT>::SkipList(unsigned int maxlevel)
{
	this->m_maxlevel = maxlevel;
	if(0 == maxlevel || maxlevel > 16)
	{
		this->m_maxlevel = 4;
	}

	this->m_listhead = new struct SkipListNode<SLKT, SLVT>(this->m_maxlevel);
}

template<class SLKT, class SLVT>
SkipList<SLKT, SLVT>::~SkipList()
{
	// todo, free whole list
}

template<class SLKT, class SLVT>
void SkipList<SLKT, SLVT>::doPrint()
{
	SkipListNode<SLKT, SLVT>* nextnode = NULL;

	unsigned int i=this->m_maxlevel;
	do
	{
		--i;
		cout<<endl<<"level "<<i<<endl;
		nextnode = this->m_listhead->m_ptlist[i];
		unsigned int nodecount=0;
		while(true)
		{
			if(NULL == nextnode)
			{
				cout<<" --> NULL";
				break;
			}
			++ nodecount;
			cout<<" --> ("<<nextnode->m_key<<","<<nextnode->m_value<<")";

			nextnode = nextnode->m_ptlist[i];
		}
		cout<<endl<<"level "<<i<<" hava "<<nodecount<<" nodes"<<endl;

	}while(i>0);
}

template<class SLKT, class SLVT>
unsigned int SkipList<SLKT, SLVT>::getRandomLevel()
{
	unsigned int modsize = 1;
	modsize = modsize<<this->m_maxlevel;
	unsigned int tmprand = ((unsigned int)rand() % modsize);

	unsigned int rtvalue = this->m_maxlevel;
	while(tmprand/2 > 0)
	{
			-- rtvalue;
			tmprand /= 2;
	}

	return rtvalue;
}

// 查询算法，如果找到thekey，返回SkipListNode指针，否则返回NULL
template<class SLKT, class SLVT>
SkipListNode<SLKT, SLVT>* SkipList<SLKT, SLVT>::doSearch(const SLKT& thekey)
{
	SkipListNode<SLKT, SLVT>* curnode = this->m_listhead;
	SkipListNode<SLKT, SLVT>* nextnode = NULL;

	// 从高层稀疏的链表开始查找
	unsigned int i=this->m_maxlevel;
	while(true)
	{
		--i;
		cout<<endl<<"in SkipList::doSearch, i="<<i;
		while(true)
		{
			nextnode = curnode->m_ptlist[i];
			if(NULL == nextnode)
			{
				// 如果前面已经无节点,在当前链表上的查询结束, 开始搜索低一层的链表
				break;
			}

			cout<<endl<<"in SkipList::doSearch, i="<<i<<", nextnode->m_key="<<nextnode->m_key;
			if(nextnode->m_key == thekey)
			{
				// 如果键已经对应上，那很happy，返回val
				return nextnode;
			}
			else if(nextnode->m_key < thekey)
			{
				// 如果下一个节点的键 比 要查询的还要小，移动到下一个节点接着查询
				curnode = nextnode;
			}
			else
			{
				// 如果下一个节点的键 比 要查询的还要大，在当前链表上的查询结束, 开始搜索低一层的链表
				break;
			}
		}

		// 如果已经查询完最低层稠密的链表,退出查找过程
		if(0 == i)
		{
			break;
		}
	}
	return NULL;
}

template<class SLKT, class SLVT>
bool SkipList<SLKT, SLVT>::doInsert(const SLKT& thekey, SLKT& thevalue, bool doReplaceValue)
{
	SkipListNode<SLKT, SLVT>** updatePtList = new SkipListNode<SLKT, SLVT>*[this->m_maxlevel];
	SkipListNode<SLKT, SLVT>* curnode = this->m_listhead;
	SkipListNode<SLKT, SLVT>* nextnode = NULL;

	// 从高层稀疏的链表开始查找
	unsigned int i=this->m_maxlevel;
	while(true)
	{
		--i;

		while(true)
		{
			updatePtList[i] = curnode;

			nextnode = curnode->m_ptlist[i];
			if(NULL == nextnode)
			{
				// 如果前面已经无节点,在当前链表上的查询结束, 开始搜索低一层的链表
				break;
			}

			if(nextnode->m_key < thekey)
			{
				// 如果下一个节点的键 比 要查询的还要小，移动到下一个节点接着查询
				curnode = nextnode;
			}
			else
			{
				// 如果下一个节点的键 大等于 要查询，在当前链表上的查询结束, 开始搜索低一层的链表
				break;
			}
		}

		// 如果已经查询完最低层稠密的链表,退出查找过程
		if(0 == i)
		{
			break;
		}
	}

	if(NULL != nextnode)
	{
		// 在链表中找到键相同的节点
		if(nextnode->m_key == thekey)
		{
			if(doReplaceValue)
			{
				nextnode->m_value = thevalue;
				return false;
			}
			else
			{
				return false;
			}
		}
	}

	unsigned int newNodeLevel = this->getRandomLevel();
	//cout<<"getRandomLevel="<<newNodeLevel<<endl;
	SkipListNode<SLKT, SLVT>* nodept = new SkipListNode<SLKT, SLVT>(newNodeLevel, thekey, thevalue);
	for(unsigned int j=0;j<newNodeLevel;++j)
	{
		nodept->m_ptlist[j] = updatePtList[j]->m_ptlist[j];
		updatePtList[j]->m_ptlist[j] = nodept;
	}
	return true;
}

template<class SLKT, class SLVT>
bool SkipList<SLKT, SLVT>::doDelete(const SLKT& thekey)
{
	SkipListNode<SLKT, SLVT>** updatePtList = new SkipListNode<SLKT, SLVT>*[this->m_maxlevel];
	SkipListNode<SLKT, SLVT>* curnode = this->m_listhead;
	SkipListNode<SLKT, SLVT>* nextnode = NULL;
	// 从高层稀疏的链表开始查找
	unsigned int i=this->m_maxlevel;
	while(true)
	{
		--i;
		while(true)
		{
			updatePtList[i] = curnode;
			nextnode = curnode->m_ptlist[i];
			if(NULL == nextnode)
			{
				// 如果前面已经无节点,在当前链表上的查询结束, 开始搜索低一层的链表
				break;
			}

			if(nextnode->m_key < thekey)
			{
				// 如果下一个节点的键 比 要查询的还要小，移动到下一个节点接着查询
				curnode = nextnode;
			}
			else
			{
				// 如果下一个节点的键 比 要查询的还要大，在当前链表上的查询结束, 开始搜索第一层的链表
				cout<<"in doDelete, i="<<i<<", nextnode->m_key="<<nextnode->m_key<<endl;
				break;
			}
		}

		// 如果已经查询完最低层稠密的链表,退出查找过程
		if(0 == i)
		{
			break;
		}
	}
	
	// 没有在链表中找到要删除的
	if(NULL == nextnode)
	{
		return false;
	}
	if(nextnode->m_key != thekey)
	{
		return false;
	}

	// nextnode is node to be delete
	for(unsigned int j=0;j<this->m_maxlevel;++j)
	{
		if(nextnode == updatePtList[j]->m_ptlist[j])
		{
			updatePtList[j]->m_ptlist[j] = nextnode->m_ptlist[j];

			if(!updatePtList[j]->m_ishead)
			{
				cout<<"in doDelete, j="<<j<<", updatePtList[j]->m_key="<<updatePtList[j]->m_key<<endl;
			}
			else
			{
				cout<<"in doDelete, j="<<j<<", updatePtList[j] is list head"<<endl;
			}

			cout<<"in doDelete, j="<<j<<", updatePtList[j]->m_ptlist[j]="<<
				((NULL == updatePtList[j]->m_ptlist[j]) ? -1 : updatePtList[j]->m_ptlist[j]->m_key)<<endl;
		}
	}

	delete nextnode;

	return true;
}

template<class SLKT, class SLVT>
long SkipList<SLKT, SLVT>::length()
{
	SkipListNode<SLKT, SLVT>* nownode = this->m_listhead->m_ptlist[0];
	long count = 0;
	while(nownode->m_ptlist[0] != NULL)
	{
		++ count;
		nownode = nownode->m_ptlist[0];
	}
	return count;
}
#endif
